package com.wc.alorithm_luogu.P1706;

import java.util.LinkedList;
import java.util.Scanner;

/**
 * @Author congege
 * @Description 全排列问题
 * https://www.luogu.com.cn/problem/P1706
 * @Date Created in 2023/9/17-15:05
 */
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
//        LinkedList<Integer> array = new LinkedList<>();
//
//        for (int i = 1; i <= n; i++) {
//            array.add(i);
//        }
//        Main main = new Main();
//        main.fullPermutation(array, array.size(), new LinkedList<>());

        Main main = new Main();
        main.fullPermutation(new boolean[n+1],new int[n],0);
    }

    public void fullPermutation(LinkedList<Integer> array, int len, LinkedList<Integer> printArray) {
        if (array.size() == 0) {
            for (int i = 0; i < len; i++) {
                System.out.printf("%5d", printArray.get(i));
            }
            System.out.println();
            return;
        }
        int size = array.size();

        /**
         * 将一号元素删除再插入到左后
         */
        for (int i = 0; i < size; i++) {
            printArray.add(array.removeFirst());
            fullPermutation(array, len, printArray);
            array.add(printArray.removeLast());
        }
    }

    public void fullPermutation(boolean[] vis, int[] printArray, int index) {
        if (index == printArray.length) {
            for (int number : printArray) {
                System.out.printf("%5d", number);
            }
            System.out.println();
            return;
        }
        int len = printArray.length;
        for (int i = 1; i <= len; i++) {
            if (!vis[i]) {
                vis[i] = true;
                printArray[index] = i;
                fullPermutation(vis, printArray, index + 1);
                vis[i] = false;
            }
        }
    }
}
